// 提交链接 https://leetcode.cn/problems/climbing-stairs/submissions/530187350/
// 70. 爬楼梯
// 完成日期： 2024.9.8
// c++ 动态规划枚举上一步所在的楼梯

class Solution {
public:
    unordered_map<int, int> dp;
    int climbStairs(int n) {
        return dfs(n);
    }
    int dfs(int i)
    {
        if (dp[i]) return dp[i];
        if (i == 0) return 1;
        if (i < 0) return 0;
        int ans = dfs(i - 1) + dfs(i - 2);
        return dp[i] = ans;
    }
};